package Algorithm.dynamicProgramming.swordOffer;

/**
 * 剑指 Offer 10- I. 斐波那契数列 https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/
 */
public class Fib {

    /**
     * f(n)%p = [f(n−1)+f(n−2)]%p = [f(n−1)%p+f(n−2)%p]%p
     */
    public int fib(int n) {
        if(n < 1) return 0;
        int dpi_2 = 0, dpi_1 = 1, dpi=1;
        for(int i = 2;i <= n;i++) {
            dpi = (dpi_1 + dpi_2) % 1000000007;
            dpi_2 = dpi_1;
            dpi_1 = dpi;
        }
        return dpi;
    }

    public static void main(String[] args) {
        new Fib().fib(95);
    }
}
